package com.wcj.tree;

public class AVL树 {
    int height(AVLTreeNode root){
        if (root == null)
            return -1;
        else return root.height;
    }

    // 左单旋转
    AVLTreeNode SingleRotateLeft(AVLTreeNode X) {
        AVLTreeNode W = X.left;
        X.left = W.right;
        W.right = X;
        X.height = Math.max(X.left.height,X.right.height) + 1;
        W.height = Math.max(W.left.height,X.height)+1;
        return W;
    }

    // 右单旋转
    AVLTreeNode singleRotateRight(AVLTreeNode W){
        AVLTreeNode X = W.right;
        W.right = X.left;
        X.left = W;
        W.height = Math.max(W.right.height,W.left.height)+1;
        X.height = Math.max(X.right.height,W.height) + 1;
        return X;
    }

    AVLTreeNode DoubleRotatewithLeft(AVLTreeNode Z){
        Z.left = singleRotateRight(Z.left);
        return SingleRotateLeft(Z);
    }

    AVLTreeNode DoubleRotatewithRight(AVLTreeNode Z){
        Z.right = SingleRotateLeft(Z.right);
        return singleRotateRight(Z);
    }

    AVLTreeNode insert(AVLTreeNode root,AVLTreeNode parent,int data){
        if (root == null){
            root = new AVLTreeNode(data);
            root.height = 0;
            root.left = null;
            root.right = null;
        }else if (data < root.val){
            root.left = insert(root.left,root,data);
            if ((root.left.height - root.right.height) == 2) {
                if (data < root.left.val){
                    root = SingleRotateLeft(root);
                }else
                    root = DoubleRotatewithLeft(root);
            }
        }else if (data > root.val) {
            root.right = insert(root.right, root, data);
            if ((root.left.height - root.right.height) == 2){
                if (data > root.right.val){
                    root = singleRotateRight(root);
                }else
                    root = DoubleRotatewithRight(root);
            }
        }
        root.height = Math.max(root.left.height,root.right.height)+1;
        return root;
    }
}
